1. Technical Field
This application generally relates to a computer system, and more particularly to techniques used in a cache within a computer system.
2. Description of Related Art
Computer systems may include different resources used by one or more host processors. Resources and host processors in a computer system may be interconnected by one or more communication connections. These resources may include, for example, data storage devices such as the Symmetrix(trademark) family of data storage systems manufactured by EMC Corporation. These data storage systems may be coupled to one or more host processors and provide storage services to each host processor. An example data storage system may include one or more data storage devices, such as those of the Symmetrix(trademark) family, that are connected together and may be used to provide common data storage for one Qr more host processors in a computer system.
A host processor may perform a variety of data processing tasks and operations using the data storage system. For example, a host processor may perform basic system I/O operations in connection with data requests, such as data read and write operations and also administrative tasks, such as data backup and mirroring operations.
Host processor systems may store and retrieve data using a storage device containing a plurality of host interface units, disk drives, and disk interface units. Such storage devices are provided, for example, by EMC Corporation of Hopkinton, Mass. and disclosed in U.S. Pat. No. 5,206,939 to Yanai et al., U.S. Pat. No. 5,778,394 to Galtzur et al., U.S. Pat. No. 5,845,147 to Vishlitzky et al., and U.S. Pat. No. 5,857,208 to Ofek. The host systems access the storage device through a plurality of channels provided therewith. Host systems provide data and access control information through the channels to the storage device and storage device provides data to the host systems also through the channels. The host systems do not address the disk drives of the storage device directly, but rather, access what appears to the host systems as a plurality of logical disk units. The logical disk units may or may nor correspond to the actual disk drives. Allowing multiple host systems to access the single storage device unit allows the host systems to share data stored therein.
Performance of a storage system may be improved by using a cache. In the case of a disk drive system, the cache may be implemented using a block of semiconductor memory that has a relatively lower data access time than the disk drive. Data that is accessed is advantageously moved from the disk drives to the cache so that the second and subsequent accesses to the data may be made to the cache rather than to the disk drives. Data that has not been accessed recently may be removed from the cache to make room for new data. Often such cache accesses are transparent to the host system requesting the data.
Data may be stored in a cache in order to increase efficiency. However, there can be a cost associated with performing cache management operations, such as storing and retrieving data from the cache.
One technique for implementing a cache is to store the data in blocks and link each of the blocks together in a doubly linked ring list referred to herein as a replacement queue. Each block of the replacement queue represents a block of data from a logical disk unit. The blocks or slots are placed in the doubly linked ring list in the order in which they are retrieved from the disk. A pointer may point to the block that was most recently added to the list. Thus, when a new block is to be added to the cache within the replacement queue, the structure of the replacement queue, in combination with the head pointer, may be used to determine the oldest block in the replacement queue that is to be removed to make room for the new block. An implementation of the replacement queue may use both a xe2x80x9cheadxe2x80x9d pointer and a xe2x80x9ctailxe2x80x9d pointer identifying, respectively, the beginning and end of the replacement queue. The xe2x80x9ctailxe2x80x9d may determine the oldest block or slot in the replacement queue. Two such pointers may be used in an replacement queue arrangement as it may be desirable in accordance with cache management schemes in which some data may remain permanently in the cache and the xe2x80x9coldestxe2x80x9d and xe2x80x9cnewestxe2x80x9d data may not be adjacent to one another. Cache management techniques are described, for example, in issued U.S. Pat. No. 5,381,539, Jan. 10, 1995, entitled xe2x80x9cSystem and Method for Dynamically Controlling Cache Managementxe2x80x9d, Yanai et al., assigned to EMC Corporation of Hopkinton, Mass., which is herein incorporated by reference, in which a data storage system has a cache controlled by parameters including: (a) a minimum number of data storage elements which must be retrieved and stored in cache memory and used by the system before the cache management system recognizes a sequential data access in progress; (b) the maximum number of tracks or data records which the cache management system is to prefetch ahead; and (c) the maximum number of sequential data elements to be stored in cache before the memory containing the previously used tracks or data records are reused or recycled and new data written to these locations. The cache memory is in a least-recently used circular configuration in which the cache management system overwrites or recycles the oldest or least recently used memory location. The cache manager provides monitoring and dynamic adjustment of the foregoing parameters.
Described in issued U.S. Pat. No. 5,592,432, Jan. 7, 1997, entitled xe2x80x9cCache Management System Using Time Stamping for Replacement Queuexe2x80x9d, Vishlitzky et al., which is herein incorporated by reference, is a system that includes a cache directory listing data elements in a cache memory and a cache manager memory including a replacement queue and data structures. A cache manager determines which data element should be removed or replaced in the cache memory based on the elapsed time the data element has been in the memory. If the elapsed time is less than a predetermined threshold, the data element will be maintained in the same location in the replacement queue saving a number of cache management operations. The predetermined threshold is established as the average fall through time (FTT) of prior data elements in the memory. A modified least-recently-used replacement procedure uses time stamps indicating real or relative time when a non-write-pending data element was promoted to the tail of the replacement queue, the most-recently used position. Also disclosed is another embodiment in which the number of times the data element is accessed while in the memory is compared to a fixed number. If the data element has been accessed more than the fixed number, it is placed at the tail of the replacement queue ensuring a longer period for the data element in the memory.
Described in U.S. Patent Application No. 5,206,939, Apr. 27, 1993, entitled xe2x80x9cSystem and Method for Disk Mapping and Retrievalxe2x80x9d, Yanai et al, which is herein incorporated by reference, is a device-by-device cache index/directory used in disk mapping and data retrieval.
Different techniques may be used to manage the cache, for example, in determining an available slot when inserting a new element into the cache. An executing processor may make multiple attempts at different slots before locating one which can be used to store new data in the cache. In systems having multiple processors, it may be desirable to have efficient techniques which seek to reduce the number of xe2x80x9ccollisionsxe2x80x9d between processors trying to obtain an available slot such that two processors don""t attempt to access the same slot or same set of slots.
In accordance with one aspect of the invention is a method executed in a computer system for determining a plurality of increment values associated with a predetermined range of values for a plurality of processors. A plurality of unique values is determined. Each of the plurality of unique values is one of: greater than and equal to a predetermined minimum value in which the predetermined range is represented from xe2x80x9c0xe2x80x9d to xe2x80x9cn-1xe2x80x9d inclusively. Each of the plurality of unique values is one of: a prime number with respect to xe2x80x9cnxe2x80x9d such that xe2x80x9cnxe2x80x9d is not divisible by any one of said plurality of unique values, xe2x80x9cnxe2x80x9d being one of: greater than and equal to twice said prime number, and a value xe2x80x9ckxe2x80x9d having an associated set of factors of xe2x80x9ckxe2x80x9d and xe2x80x9cn-kxe2x80x9d such that each factor in the set is greater than the predetermined minimum value and each of the factors is unique with respect to every other factor of all other sets of factors associated with all others of said plurality of unique values, and xe2x80x9ckxe2x80x9d is less than xe2x80x9cnxe2x80x9d.
In accordance with another aspect of the invention is a computer program product for determining a plurality of increment values associated with a predetermined range of values for a plurality of processors. The computer program product includes machine executable code that determines a plurality of unique values, each of the plurality of unique values being one of: greater than and equal to a predetermined minimum value, the predetermined range being represented from xe2x80x9c0xe2x80x9d to xe2x80x9cn-1xe2x80x9d inclusively. Each of the plurality of unique values is one of: a prime number with respect to xe2x80x9cnxe2x80x9d such that xe2x80x9cnxe2x80x9d is not divisible by any one of the plurality of unique values, xe2x80x9cnxe2x80x9d being one of: greater than and equal to twice said prime number, and a value xe2x80x9ckxe2x80x9d having an associated set of factors of xe2x80x9ckxe2x80x9d and xe2x80x9cn-kxe2x80x9d such that each factor in the set is greater than the predetermined minimum value and each of the factors is unique with respect to every other factor of all other sets of factors associated with all others of the plurality of unique values, xe2x80x9ckxe2x80x9d being less that xe2x80x9cnxe2x80x9d.